package _线性;

import java.util.*;

public class _Array {
    //189:轮转数组 https://leetcode.cn/problems/
    //  原地算法
    public void rotate(int [] nums, int k) {
        // 反转数组
        k %= nums.length;
        // 先对整个数组进行一次翻转
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
            l++;
            r--;
        }
    }


    // 169:寻找数组中的多数元素，
    // 要求 空间复杂度O(1)，时间复杂度O(n)
    public int majorityElement(int[] nums) {
        int count = 0;
        int ans = 0;
        for (int num : nums) {
            if (count == 0)
                ans = num;
            count += (num == ans) ? 1 : -1;
        }
        return ans;
    }

    // 2404:出现最频繁的偶数元素 https://leetcode.cn/problems/most-frequent-even-element/description/
    // map存的是 偶数元素 以及其出现的次数


    // 56：todo 100题 合并区间：https://leetcode.cn/problems/merge-intervals/description/
    public int[][] merge(int[][] intervals) {

        return null;
    }

    // （原地哈希置换的思维）
    // ============================================================================
    // 41: 缺失的第一个正数  https://leetcode.cn/problems/first-missing-positive/
    // 将每个正整数 x 尽可能地放到索引 x - 1 的位置上。
    // nums[i] ——> nums[nums[i] - 1]
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 可能需要多次交换才能正确归位
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int x = nums[i];
                nums[i] = nums[x - 1];
                nums[x - 1] = x;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }

    // 442：数组中重复的数据：https://leetcode.cn/problems/find-all-duplicates-in-an-array/
    // 标记法：把每个 x 对应的位置 num[x-1]标记成负数
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();

        for (int x : nums) {
            int idx = Math.abs(x) - 1;
            if (nums[idx] < 0) {
                res.add(Math.abs(x)); // 第二次访问，说明重复
            } else {
                nums[idx] = -nums[idx];     // 第一次访问，取负数标记
            }
        }
        return res;
    }

    // 448 ：找到数组中所有消失的数据：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/
    // 标记法：把每个 x 对应的位置 num[x-1]标记成负数
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();

        for (int x : nums) {
            int idx = Math.abs(x) - 1;
            if (nums[idx] <= 0)     // 表示有重复的元素
                continue;
            nums[idx] = -nums[idx]; // 第一次访问，把出现过的位置标记成负数
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0)
                res.add(i + 1);     // 第二次访问，正数的位置即是没有出现的
        }
        return res;
    }

    // 645 ：错误的集合：https://leetcode.cn/problems/set-mismatch/description/
    // 将每个正整数 x 尽可能地放到索引 x - 1 的位置上。
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 可能需要多次交换才能正确归位
            while (nums[nums[i] - 1] != nums[i]) {
                int x = nums[i];
                nums[i] = nums[x - 1];
                nums[x - 1] = x;
            }
        }   //元素已经排序了[2，4，1，4] ——> [1,2,4,4]

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return new int[]{nums[i], i + 1};
        }
        return new int[]{-1, -1};
    }

    // 计数
    public int[] findErrorNums_(int[] nums) {
        int n = nums.length + 1;
        int[] count = new int[n];

        for (int num : nums)
            count[num]++;

        int dup = -1, miss = -1;
        for (int i = 1; i < n; i++) {
            if (count[i] == 0) miss = i;
            if (count[i] == 2) dup = i;
        }

        return new int[]{dup, miss};
    }

    //------------------------------------------------------------
}












